package _2_2基础算法;

import java.util.Scanner;

public class _3382前缀和 {
	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();// 数组长度
		int m = scan.nextInt();// 查询次数
		int arr[] = new int[n];
		long sum[][] = new long[6][n+1];// 存储前缀和
		int query[][] = new int[m][3]; // m行3列 用于存储输入的查询条件
		long modNum = (long)1e9+7;
		
		// 接收数组
		for(int i = 0;i < n;i++) {
			arr[i] = scan.nextInt();
		}
		
		
		// 接收m次查询
		for(int i = 0;i < m;i++) {
			for(int j = 0;j < 3;j++) {
				query[i][j] = scan.nextInt();
			}
		}
		
		// 对数组进行前缀和预处理存入sum中
		// 每次都会取arr[i]与之前的sum总和进行相加，所以sum[i]就是前i项的和
		// sum[i] = sum[i-1] + arr[i]
		
		// 题目中说明了k不大于5，所以我们可以把所有次方的结果进行预处理计算
		// i代表k次方 j是列，代表每个k次方行，对每一行的所有元素进行k次方
		for(int i = 1;i < 6;i++) {
			for(int j = 1;j <= n;j++) {
				sum[i][j] = (long) (sum[i][j-1] + Math.pow(arr[j-1], i));
			}
		}
		
		// 进行m次查询
		for(int i = 0;i < m;i++) {
			int l = query[i][0];
			int r = query[i][1];
			int k = query[i][2];
			// 需要减去的是L前面的值，而不是L，所以L-1
			long total = (sum[k][r] - sum[k][l-1]) % modNum; 
			System.out.println(total);
		}

        scan.close();
		
	}
}
